package com.xdja.testxlog;

public class TestPalindrome {

    public static void main(String[] args) {

       boolean result = test("012343210");
        String text = !result?"不是":"是";
        System.out.println("这"+text+"回文字符串");

    }
    public static boolean test(String arg){

        //准备数据
        Node headNode = prepData(arg);
        //获取中结点
        Node middleNode = getMiddleNode(headNode);
        //将后半段逆序
        Node reverseNode = reverseNode(middleNode);
        //判断是否为回文
        boolean palindrome = isPalindrome(headNode, reverseNode);
        return palindrome;
    }

    public static Node prepData(String str){

        String test = str;
        char [] a = test.toCharArray();
        //拼接链表：
        Node headNode = new Node(String.valueOf(a[0]));
        Node current = headNode;
        for (int i = 1; i < a.length; i++) {
            Node temp = new Node(String.valueOf(a[i]));
            current.setNext(temp);
            current = temp;
        }
        return headNode;
    }

    public static Node getMiddleNode(Node headNode){
        Node lowlyNode = headNode.getNext();
        Node fastNode = null;
        if(lowlyNode != null){
            fastNode = lowlyNode.getNext();
        }
        while (fastNode != null){
            if(fastNode.getNext() == null){
                //说明链表长度为奇数
                //说明此时lowlyNode为中间结点
                return lowlyNode;
            }

            if(fastNode.getNext().getNext() == null){
                //说明链表长度为偶数
                //此时应该根据规定（看你的需求）来返回上中结点还是下中结点
                //假设链表长度为4（0，1，2，3）
                //上中结点就是1，下中结点就是2
                //此处我返回下中结点
                return lowlyNode.getNext();
            }
            //每次循环，快指针前进两步
            fastNode = fastNode.getNext();
            fastNode = fastNode.getNext();
            //每次循环，慢指针前进一步
            lowlyNode = lowlyNode.getNext();
        }

        return lowlyNode;
    }

    public static Node reverseNode(Node head){
        Node temp = head.getNext();
        Node flag = temp.getNext();

        head.setNext(null);

        while (flag != null){
            temp.setNext(head);

            //temp 变成了头
            head = temp;
            //flag 变成了 temp
            temp = flag;

            flag = flag.getNext();
        }

        temp.setNext(head);
        return temp;
    }

    /**
     * @param head  头结点
     * @param middleHead <p>若链表长度为奇数，则在中间结点的 next 结点开始逆序，
     *                   若链表长度为偶数，则在下中结点开始逆序<p/>
     * @return
     */
    public static boolean isPalindrome(Node head, Node middleHead){

        /**
         * middleHead肯定是在head后面的
         * 也就是 middleHead 会先走到结尾，所以此处用 middleHead 来判断
         */
        while (middleHead != null){
            if(!head.getData().equals(middleHead.getData())){
                return false;
            }

            head = head.getNext();
            middleHead = middleHead.getNext();
        }

        return true;
    }

    static class Node {
        String data;
        Node next;
        
        public Node(String data) {
            this.data = data;
        }
        
        public String getData() {
            return data;
        }
        
        public void setData(String data) {
            this.data = data;
        }
        
        public void setNext(Node next) {
            this.next = next;
        }
        
        public Node getNext(){
            return next;
        }
    }

}
